#include<bits/stdc++.h>
#include <cmath>
#include <cstring>
#include <string>
struct control {
    int ct, val;
    control(int Ct, int Val = -1)
        : ct(Ct)
        , val(Val)
    {
    }
    inline control operator()(int Val)
    {
        return control(ct, Val);
    }
} _endl(0), _prs(1), _setprecision(2);
struct FastIO {
#define IOSIZE 1000000
    char in[IOSIZE], *p, *pp, out[IOSIZE], *q, *qq, ch[20], *t, b, K, prs;
    FastIO()
        : p(in)
        , pp(in)
        , q(out)
        , qq(out + IOSIZE)
        , t(ch)
        , b(1)
        , K(6)
    {
    }
    ~FastIO()
    {
        flush();
    }
    void flush()
    {
        fwrite(out, 1, q - out, stdout);
        q = out;
    }
    inline char getch()
    {
        return p == pp && (pp = (p = in) + fread(in, 1, IOSIZE, stdin), p == pp) ? b = 0, EOF : *p++;
    }
    inline void putch(char x)
    {
        q == qq && (fwrite(out, 1, q - out, stdout), q = out), *q++ = x;
    }
    inline void puts(const char str[])
    {
        fwrite(out, 1, q - out, stdout), fwrite(str, 1, strlen(str), stdout), q = out;
    }
    inline void getline(std::string& s)
    {
        s = "";
        for (char ch; (ch = getch()) != '\n' && b;)
            s += ch;
    }
#define indef(T)                                               \
    inline FastIO& operator>>(T& x)                            \
    {                                                          \
        x = 0;                                                 \
        char f = 0, ch;                                        \
        while (!isdigit(ch = getch()) && b)                    \
            f |= ch == '-';                                    \
        while (isdigit(ch))                                    \
            x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch(); \
        return x = f ? -x : x, *this;                          \
    }
    indef(int) indef(long long) inline FastIO& operator>>(char& ch)
    {
        return ch = getch(), *this;
    }
    inline FastIO& operator>>(std::string& s)
    {
        s = "";
        char ch;
        while (isspace(ch = getch()) && b)
            ;
        while (!isspace(ch) && b)
            s += ch, ch = getch();
        return *this;
    }
    inline FastIO& operator>>(double& x)
    {
        x = 0;
        char f = 0, ch;
        double d = 0.1;
        while (!isdigit(ch = getch()) && b)
            f |= (ch == '-');
        while (isdigit(ch))
            x = x * 10 + (ch ^ 48), ch = getch();
        if (ch == '.')
            while (isdigit(ch = getch()))
                x += d * (ch ^ 48), d *= 0.1;
        return x = f ? -x : x, *this;
    }
#define outdef(_T)                                            \
    inline FastIO& operator<<(_T x)                           \
    {                                                         \
        !x && (putch('0'), 0), x < 0 && (putch('-'), x = -x); \
        while (x)                                             \
            *t++ = x % 10 + 48, x /= 10;                      \
        while (t != ch)                                       \
            putch(*--t);                                      \
        return *this;                                         \
    }
    outdef(int) outdef(long long) inline FastIO& operator<<(char ch)
    {
        return putch(ch), *this;
    }
    inline FastIO& operator<<(const char str[])
    {
        return puts(str), *this;
    }
    inline FastIO& operator<<(const std::string& s)
    {
        return puts(s.c_str()), *this;
    }
    inline FastIO& operator<<(double x)
    {
        int k = 0;
        this->operator<<(int(x));
        putch('.');
        x -= int(x);
        prs && (x += 5 * pow(10, -K - 1));
        while (k < K)
            putch(int(x *= 10) ^ 48), x -= int(x), ++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl)
    {
        switch (cl.ct) {
        case 0:
            putch('\n');
            break;
        case 1:
            prs = cl.val;
            break;
        case 2:
            K = cl.val;
            break;
        }
        return *this;
    }
    inline operator bool()
    {
        return b;
    }
} io;
using namespace std;
#define ll long long
#define ull unsigned long long
#define str string
#define all(x) (x).begin(),(x).end()
#define ms(a,t) memset(a,t,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define db double
const int maxn = 5e6+10;
const int mod = 998244353;
const ll INF = 0x3f3f3f3f;
const db eps = 1e-7;
int n,m,q;
int fa[maxn],siz[maxn];
int find(int x) {
	return ((fa[x] == x) ? x : (fa[x] = find(fa[x])));
}
void merge(int x,int y) {
	x = find(x); y = find(y);
	if(x == y) return;
	if(siz[x] > siz[y]) swap(x,y);
	fa[x] = y; siz[y] += siz[x];
}
int a[maxn],tot;
vector<int> vec[maxn];
int pre[maxn],pos[maxn];
void Solve() {
	io >> n >> m >> q;
	for(int i = 1; i <= n; i++) {
		fa[i] = i; siz[i] = 1;
	}
	for(int i = 1,u,v; i <= m; i++) {
		io >> u >> v;
		merge(u,v);
	}
	for(int i = 1; i <= n; i++) if(fa[i] == i) {
		a[i] = ++tot;
	}
	for(int i = 1; i <= n; i++) {
		a[i] = a[find(i)];
		if(vec[a[i]].size()) pre[i] = vec[a[i]].back();
		vec[a[i]].pb(i); pos[i] = vec[a[i]].size()-1;
	}
	for(int i = 1,l,r; i <= q; i++) {
		io >> l >> r;
		int cnt = 0,lst = 0;
		set<int> st;
		for(int j = l; j <= r; j++) {
			if(pre[j] < l) cnt++,lst = j;
		}
		for(int j = l; j <= lst; j++) {
			st.erase(pre[j]); st.insert(j);
		}
		int ret = lst-*st.begin()+1;
		for(int j = lst+1; j <= r; j++) {
//			assert(st.count(pre[j]) || (cerr<<l<<' '<<j<<' '<<pre[j]<<' '<<*st.lower_bound(pre[j])<<'\n',0));
//			assert(st.size() == cnt);
			st.erase(pre[j]); st.insert(j);
			ret = min(ret,j-*st.begin()+1);
		}
		cout<<ret<<'\n';
	}
	
}
int main() {
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	int T; cin >> T; while(T--)
	Solve();
	return 0;
}
